﻿#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

typedef struct
{
	char name[256];
	int times;
}DynamicMostTopKNameData;

static unordered_map<string, DynamicMostTopKNameData*> nameMap;
static unordered_map<string, int> nameIndexMap;
static unordered_map<int, string> indexNameMap;
static int heapSize = 0;

static void swap(const char* name1, const char* name2)
{
	if (strcmp(name1, name2) == 0) return;

	auto pair1 = nameIndexMap.find(name1);
	auto pair2 = nameIndexMap.find(name2);
	auto index1 = pair1->second;
	auto index2 = pair2->second;
	nameIndexMap[name2] = index1;
	nameIndexMap[name1] = index2;
	indexNameMap[index1] = name2;
	indexNameMap[index2] = name1;
}

static void heapify(const char* name)
{
	auto data = nameMap[name];
	auto index = nameIndexMap[name];
	while (index >= 0)
	{
		int upIndex = (index - 1) / 2;
		if (upIndex == index) break;

		auto upName = indexNameMap[upIndex];
		auto upData = nameMap[upName];
		if (data->times > upData->times)
		{
			swap(name, upName.c_str());
			index = upIndex;
		}
		else
		{
			break;
		}
	}
}

#define MAX(a, b) (a > b ? a :b)

static string pop()
{
	if (heapSize == 0) return "";

	auto first = indexNameMap[0];
	auto last = indexNameMap[heapSize - 1];
	swap(first.c_str(), last.c_str());
	--heapSize;
	
	// heap insert
	auto data = nameMap[last];
	int index = 0;
	while (index < heapSize)
	{
		int left = index * 2 + 1;
		int right = index * 2 + 2;
		if (left < heapSize && right < heapSize)
		{
			auto leftName = indexNameMap[left];
			auto leftData = nameMap[leftName];
			auto rightName = indexNameMap[right];
			auto rightData = nameMap[rightName];
			if (data->times < MAX(leftData->times, rightData->times))
			{
				if (leftData->times > rightData->times)
				{
					swap(leftName.c_str(), last.c_str());
					index = left;
				}
				else
				{
					swap(rightName.c_str(), last.c_str());
					index = right;
				}
			}
			else
			{
				break;
			}
		}
		else if (left < heapSize)
		{
			auto leftName = indexNameMap[left];
			auto leftData = nameMap[leftName];
			if (data->times < leftData->times)
			{
				swap(leftName.c_str(), last.c_str());
				index = left;
			}
			else
			{
				break;
			}
		}
		else
		{
			break;
		}
	}

	return first;
}

static void recover(const char* name)
{
	if (strlen(name) == 0) return;

	auto data = nameMap[name];
	auto index = nameIndexMap[name];
	++heapSize;
	auto lastName = indexNameMap[heapSize - 1];
	swap(name, lastName.c_str());
	heapify(name);
}

static void addName(const char* name)
{
	auto exists = nameMap.find(name);
	if (exists == nameMap.end())
	{
		auto data = new DynamicMostTopKNameData();
		strcpy_s(data->name, name);
		data->times = 1;
		nameMap[name] = data;
		nameIndexMap[name] = heapSize++;
		indexNameMap[heapSize - 1] = name;
	}
	else
	{
		exists->second->times++;
		heapify(name);
	}
}

static void clearNameMap()
{
	for (auto it = nameMap.begin(); it != nameMap.end(); ++it)
	{
		delete(it->second);
	}

	nameMap.clear();
	nameIndexMap.clear();
	indexNameMap.clear();
}

// 不停的输入字符串，每次输入字符串之后，需要统计输入的所有字符串中出现次数最多的前K个字符串。
//
// 比如，每次输入一个字符串，输入之后，需要实时查看出现最多的前K个字符串。
//
// 思路：
// 使用自定义小根堆，因为需要修改堆中节点的次数，然后动态调整堆结构。
int main_DynamicMostTopK()
{
	char names[][256] = {
		"dog",
		"apple",
		"horse",
		"tiger",
		"horse",
		"dog",
		"box",
		"banana",
		"plan",
		"plan",
		"plan",
	};

	for (int i = 0; i < sizeof(names) / 256; i++)
	{
		addName(names[i]);
		printf("%d:\n", i);
		auto top = pop();
		printf("%s\n", top.c_str());
		auto top2 = pop();
		printf("%s\n", top2.c_str());
		auto top3 = pop();
		printf("%s\n", top3.c_str());

		recover(top.c_str());
		recover(top2.c_str());
		recover(top3.c_str());
	}

	clearNameMap();
	return 0;
}